Définition :
Soit \(\sigma\) une permutation de taille \(n\)
L'entier \(1\leqslant i\leqslant n\) est un point fixe de \(\sigma\) si et seulement si \(\sigma(i)=i\)
Propriété :
Soit \(F_n\) le nombre de points fixes d'une permutation uniforme aléatoire de taille \(n\) \(S_n\)
Pour chaque \(n\), on a : $$E(F_n)={{1}}\quad\text{ et }\quad\operatorname{Var}(F_n)={{1}}$$
Nombre de cycles disjoints
Théorème :
Toute permutation \(\sigma\) se décompose de façon unique en composés de cycles à supports disjoints
De plus, ce composé est commutatif
Notation :
On note \(\#\sigma\) le nombre de cycles de la permutation \(\sigma\)
Proposition :
Soit \(C_n\) le nombre de cycles disjoints d'une permutation aléatoire uniforme de taille \(n\) \(S_n\)
Quand \(n\to+\infty\), on a : $$E(C_n)\underset{+\infty}\sim{{\ln(n)}}$$
Plus longue sous-suite
Proposition :
Soit \(\sigma\) une permutation aléatoire suivant la loi uniforme
On définit \(L(\sigma)\) comme la variable aléatoire donnant la taille de la plus grande sous-suite croissante de \(\sigma\)
On définit \(\ell_n\) comme la moyenne de \(L(\sigma)\) sur toutes les permutations de taille \(n\) $$\ell_n=\frac1{n!}\sum_{\sigma\in S_n}L(\sigma)\quad\text{ pour }\quad n\in{\Bbb N}$$
Alors, quand \(n\to+\infty\), on a : $$\ell_n=2\sqrt n+cn^{1/6}+o(n^{1/6})$$avec \(c=-1.77108\dots\) une constante avec une définition compliquée|\(\ell_n\)
Loi d'Ewens
(Loi d'Ewens)
Soit \(\sigma_n\) une permutation aléatoire suivant la loi d'Ewens de paramètre \(\lambda\) générée par l'algorithme des restaurants chinois
On note : $$\xi_k:={{\begin{cases}1&\text{si}\quad\text{si le client }k\text{ s'assoit à une nouvelle table}\\ 0&\text{sinon.}&\end{cases}}}$$
Alors $$\xi_k\sim{{\mathcal{Ber}\left(\frac\theta{\theta+k-1}\right)}}$$
Soit \(\sigma_n\) une permutation aléatoire suivant la loi d'Ewens de paramètre \(\lambda\)
Alors $$\Bbb E(\#\sigma_n)\sim{{\theta\ln(n)}}$$
Soit \(\sigma_n\) une permutation aléatoire suivant la loi d'Ewens de paramètre \(\lambda\)
Alors $$\operatorname{Var}(\#\sigma_n)\sim{{\theta\ln(n)}}$$
Soit \(\sigma_n\) une permutation aléatoire suivant la loi d'Ewens de paramètre \(\lambda\)
Soit \(A_{n,i}\) le nombre de cycles de longueur \(i\) de \(\sigma\)
Alors $$\Bbb P_\theta(A_{n,1}=a_1,\dots,A_{n,n}=a_n)= {{\frac{n!}{\theta(n)}\prod^n_{j=1}\frac1{a_j!}\left(\frac\theta j\right)^{a_j} }}$$